
// Definition for a binary tree node.
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

#include <unordered_map>
using namespace std;
class Solution
{
public:
    int target = 0;
    long long res = 0;
    void count_path(TreeNode *root, long long sum, unordered_map<long long, int> &sum_map)
    {
        if (!root)
            return;
        // 前缀和 表示从根+..+到当前节点
        sum += root->val;
        // 如果 sum-target出现过 说明从加入哈希表的节点后一个到当前节点的值为target
        res += sum_map[sum - target];
        sum_map[sum]++;
        count_path(root->right, sum, sum_map), count_path(root->left, sum, sum_map);
        // 回溯 这个路径已经失效了
        sum_map[sum]--;
    }
    int pathSum(TreeNode *root, int targetSum)
    {
        target = targetSum;
        // 初始化为{{0,1}} 表示从根节点开始
        unordered_map<long long, int> sum_map{{0, 1}};
        count_path(root, 0, sum_map);
        return res;
    }
};